/*
Copyright (c) 2012 by karmaleaving@qq.com. All rights RESERVED.
*/
/*
This file defines a single-track-list that has forward iterator.
The "slist" has less operation (no push/pop_back) than list, 
while use less space.
Both insertion and erasing effect the element after the iterator.
You can use "insert_after(end(), ...)" to insert before first element
and	use "erase_after(end(), ...)" to erase the first element.

The "slist" is not in standard lib.
*/
#ifndef __STD_FWD_LIST_H_VERSION_KL__
#define __STD_FWD_LIST_H_VERSION_KL__

#include "memory.h"
#include "functional.h"

#define _KL_USE_FWD_LIST_
#define _USE_FWD_LIST_BACKUP_BUF

KL_BEGIN
#ifdef _KL_USE_FWD_LIST_
// CLASS slist {
template<typename Type, typename Allocate = KL::allocator<Type>>
class slist
{
public:
	KL_TYPE_DEFINE(Type);
protected:
	struct _node_base_;
	struct _node_data_;
	struct _iterator_;
	typedef _node_base_ node_type;
	typedef node_type * _node_pointer;
	typedef _memory_helper_<value_type> _helper;
public:
	STD_ITERATOR_DEFINE(_iterator_);
	typedef typename Allocate::rebind<_node_base_>::other node_allocator_type;
	typedef typename Allocate::rebind<_node_data_>::other allocator_type;
protected:
	static const size_type _MIN_BACKUP_SIZE = 16;
	mutable _node_pointer _backup;
	mutable size_type _backup_size;
	_node_pointer _tail;
	size_type _size;
	node_allocator_type _node_alloc;
	allocator_type _alloc;
public:
	slist()
		: _size(0)
		, _backup_size(0)
		, _backup(0)
	{
		this->_init_tail();
	}
	slist(slist const &o)
		: _size(0)
		, _backup_size(0)
		, _backup(0)
	{
		this->_init_tail();
		if(o._backup_size != 0)
		{
			KL::swap(_backup, o._backup);
			KL::swap(_backup_size, o._backup_size);
		}
		if(o._size == 0) return;
		this->_insert_after_i(_tail, o._size, o.begin());
	}
	slist(size_type num, const_reference value)
		: _size(0)
		, _backup_size(0)
		, _backup(0)
	{
		this->_init_tail();
		if(num == 0) return;
		this->_insert_after(_tail, num, value);
	}
	template<typename InIter>
	slist(InIter first, InIter last)
		: _size(0)
		, _backup_size(0)
		, _backup(0)
	{
		this->_init_tail();
		size_type num = KL::distance(first, last);
		this->_insert_after_i(_tail, num, first);
	}
	void swap(slist &o)
	{
		swap(this->_tail, o._tail);
		swap(this->_size, o._size);
	}
	void reverse()
	{
		if(_size <= 1) return;
		_node_pointer prev = _tail;
		_node_pointer node = _tail->next;
		do {
			_node_pointer next = node->next;
			node->next = prev;
			prev = node;
			node = next;
		} while(node != _tail);
		_tail->next = prev;
	}
	void clear()
	{
		this->_erase_after(_size, _tail);
	}
	void resize(size_type size, const_reference value)
	{
		if(size < _size)
		{
			_erase_after(_size - size, _tail);
		}
		else if(size > _size)
		{
			this->_insert_after(_tail, size - _size, value);
		}
	}
	~slist()
	{
		ASSERT_REPAIR(_tail, return);
		this->_erase_after(_size, _tail);
		_tidy_tail();
		_tidy();
	}
	slist & operator = (slist const &o)
	{
		if(&o == this) return *this;
		this->_erase_after(_size, _tail);
		this->_insert_after_i(_tail, o._size, o.begin());
		return *this;
	}
	void assign(size_type num, value_type const value)
	{
		this->_erase_after(_size, _tail);
		this->_insert_after(_tail, num, value);
	}
	template<typename InIter>
	void assign(InIter first, InIter last)
	{	// dont assign self.
		size_type num = distance(first, last);
		this->_erase_after(_size, _tail);
		this->_insert_after_i(_tail, num, first);
	}
	void erase_after(iterator pos)
	{
		ASSERT_REPAIR(_valid_data(pos), return);
		this->_erase_after(pos._node);
	}
	void erase_after(_iterator_ from, size_type num)
	{
		ASSERT_REPAIR(_size >= num, return);
		while(num--)
		{			
			ASSERT_REPAIR(_valid_data(from), return);
			this->_erase_after(from._node);
		}
	}
	void insert_after(_iterator_ pos, const_reference value)
	{
		this->_insert_after(pos._node, value);
		return pos._node->next;
	}
	void insert_after(_iterator_ pos, size_type num, const_reference value)
	{
		this->_insert_after(pos._node, num, value);
	}
	template<typename InIter>
	void insert_after(_iterator_ pos, InIter first, InIter last)
	{
		size_type num = KL::distance(first, last);
		this->_insert_after_i(pos._node, num, first);
	}
	void push_front(const_reference value)
	{
		this->_insert_after(_tail, value);
	}
	void pop_front()
	{
		ASSERT_REPAIR(_size, return);
		_erase_after(_tail);
	}
	bool empty() const
	{
		return _size == 0;
	}
	size_type size() const
	{
		return _size;
	}
	iterator begin()
	{
		return iterator(_make_iterator(_tail->next));
	}
	iterator end()
	{
		return iterator(_make_iterator(_tail));
	}
	const_iterator begin() const
	{
		return iterator(_make_iterator(_tail->next));
	}
	const_iterator end() const
	{
		return iterator(_make_iterator(_tail));
	}
	reverse_iterator rbegin()
	{
		return reverse_iterator(_make_iterator(_tail->prev));
	}
	reverse_iterator rend()
	{
		return reverse_iterator(_make_iterator(_tail));
	}
	const_reverse_iterator rbegin() const
	{
		return reverse_iterator(_make_iterator(_tail->prev));
	}
	const_reverse_iterator rend() const
	{
		return reverse_iterator(_make_iterator(_tail));
	}
	reference front()
	{
		return _visit(_tail->next);
	}
	const_reference front() const
	{
		return _visit(_tail->next);
	}
	allocator_type get_allocator() const
	{
		return _alloc;
	}
	size_type max_size() const
	{
		return _allocator::max_size();
	}
	// special.
	void remove(const_reference value)
	{
		remove_if(KL::bind1st(KL::equal_to<value_type>(), value));
	}
	template<typename Bool>
	void remove_if(Bool fun)
	{
		_node_pointer node = _tail;
		while(node->next != _tail)
		{
			if(fun(_visit(node->next)))
			{
				this->_erase_after(node);
			}
			else node = node->next;
		}
	}
protected:
	// PROTECTED {
	// OPERATE {
	void _join_after(_node_pointer pos, _node_pointer in)
	{
		_link(in, pos->next);
		_link(pos, in);
		++_size;
	}
	void _unjoin_after(_node_pointer out)
	{
		_link(out, out->next->next);
		--_size;
	}
	void _join_after(_node_pointer pos, size_type num, _node_pointer front, _node_pointer back)
	{
		_link(back, pos->next);
		_link(pos, front);
		_size += num;
	}
	void _unjoin_after(_node_pointer pos, size_type num, _node_pointer back)
	{
		_link(pos, back->next);
		_size -= num;
	}
	void _assign(_node_pointer pos, const_reference value)
	{
		_helper::raw_fill(&_visit(pos), value);
	}
	void _assign(_iterator_ pos, size_type num, const_reference value)
	{
		_helper::raw_fill_n(pos, num, value);
	}
	template<typename InIter>
	void _assign_i(_iterator_ pos, size_type num, InIter &first)
	{
		_helper::raw_copy_n(first, num, pos);
	}
	void _destroy(_node_pointer pos)
	{
		_helper::destroy(&_visit(pos));
	}
	void _destroy(_iterator_ pos, size_type num)
	{
		_helper::destroy_n(pos, num);
	}
protected: // insert , erase.
	void _insert_after(_node_pointer pos, const_reference data)
	{
		_node_pointer node;
		this->_allocate(node);
		this->_assign(node, data);
		this->_join_after(pos, node);
	}
	void _insert_after(_node_pointer pos, size_type num, const_reference data)
	{
		if(num == 0) return;
		_node_pointer front, back;
		this->_allocate(num, front, back);
		this->_assign(front, num, data);
		this->_join_after(pos, num, front, back);
	}
	template<typename InIter>
	void _insert_after_i(_node_pointer pos, size_type num, InIter data)
	{
		if(num == 0) return;
		_node_pointer front, back;
		this->_allocate(num, front, back);
		this->_assign_i(front, num, data);
		this->_join_after(pos, num, front, back);
	}
	void _erase_after(_node_pointer pos)
	{
		_node_pointer temp = pos->next;
		this->_unjoin_after(pos);
		this->_destroy(temp);
		this->_deallocate(temp);
	}
	void _erase_after(size_type num, _node_pointer pos)
	{
		if(num == 0) return;
		_node_pointer back = _forward(pos, num);
		_node_pointer front = pos->next;
		_destroy(front, num);
		_unjoin_after(pos, num, back);
		_deallocate(num, front, back);
	}
	// OPERATE }
	// ALLOCATE {
	bool _backup_full() const
	{
		return _backup_size > _MIN_BACKUP_SIZE && _backup_size >= (_size >> 1);
	}
	void _init_tail()
	{
		_tail = _node_alloc.allocate(1);
		_link(_tail, _tail);
	}
	void _tidy_tail()
	{
		_node_alloc.deallocate(_tail, 1);
	}
	void _allocate_node_data(_node_pointer &out)
	{
		out = _allocator::allocate(1);
	}
	void _deallocate_node_data(_node_pointer &in)
	{
		_allocator::deallocate(static_cast<_node_data_*>(in), 1);
	}
	void _allocate(_node_pointer &out)
	{
		if(_backup_size)
		{
			--_backup_size;
			out = _backup;
			_backup = _backup->next;
		}
		else _allocate_node_data(out);
	}
	void _deallocate(_node_pointer in)
	{
		if(!_backup_full())
		{
			++_backup_size;
			_safe_link(in, _backup);
			_backup = in;
		}
		else _deallocate_node_data(in);
	}
	void _allocate(size_type num, _node_pointer &front, _node_pointer &back)
	{
		if(num == 0) return;
		if(_backup_size >= num)
		{
			_backup_size -= num;
			front = _backup;
			back = _forward(_backup, num - 1);
			_backup = back->next;
			return;
		}		
		if(_backup_size)
		{
			front = _backup;
			back = _forward(_backup, _backup_size - 1);
			num -= _backup_size;
			_backup = 0;
			_backup_size = 0;
		}
		else
		{
			_allocate_node_data(front);
			back = front;
			--num;
		}
		_node_pointer node;
		while(num--)
		{
			_allocate_node_data(node);
			_link(back, node);
			back = back->next;
		}
	}
	void _deallocate(size_type num, _node_pointer front, _node_pointer back)
	{
		if(!_backup_full())
		{
			_backup_size += num;
			_safe_link(back, _backup);
			_backup = front;
		}
		else
		{
			while(--num)
			{
				_node_pointer node = front;
				front = front->next;
				_deallocate_node_data(node);
			}
			_deallocate_node_data(front);
		}
	}
	void _tidy()
	{
		if(_backup_size == 0) return;
		while(--_backup_size)
		{
			_node_pointer node = _backup;
			_backup = _backup->next;
			_deallocate_node_data(node);
		}
		_deallocate_node_data(_backup);
		_backup = 0;
	}
	// ALLOCATE }
	// FAST FUNCTION {
	_iterator_ _make_iterator(_node_pointer node) const
	{
		return _iterator_(node, (slist*)this);
	}
	bool _valid_iterator(_iterator_ const &iter) const
	{
		return iter._container == this;
	}
	bool _valid_data(_iterator_ const &iter) const
	{
		return iter._container == this && iter._node->next != _tail;
	}
	static value_type &_visit(_node_base_ * node) 
	{
		return static_cast<_node_data_*>(node)->data;
	}
	_node_pointer _forward(_node_pointer in, size_type num)
	{
		while(num--) in = in->next;
		return in;
	}
	void _link(_node_pointer prev, _node_pointer next)
	{
		prev->next = next;
	}
	void _safe_link(_node_pointer prev, _node_pointer next)
	{
		if(prev) prev->next = next;
	}
	// FAST FUNCTION }
	// INNER CLASS {
	struct _node_base_
	{
		_node_base_ * next;
	};
	struct _node_data_ : public _node_base_
	{
		value_type data;
	};
	class _iterator_ 
		: public KL::iterator<KL::forward_iterator_tag, value_type>
	{
		friend class slist;
	private:
		_node_base_ * _node;
		slist * _container;
		_iterator_(_node_base_ * node, slist * l = 0)
			: _node(node), _container(l)
		{
		}
	public:
		_iterator_() : _node(0)
		{
		}
		_iterator_(_iterator_ const &o)
			: _node(o._node), _container(o._container)
		{
		}
		_iterator_ & operator ++()
		{
			_node = _node->next;
			return *this;
		}
		_iterator_ operator ++(int)
		{
			_iterator_ temp = *this;
			_node = _node->next;
			return temp;
		}
		reference operator *()
		{
			return _visit(_node);
		}
		pointer operator ->()
		{
			return &_visit(_node);
		}
		bool operator == (_iterator_ const &o) const
		{
			ASSERT_REPAIR(_container == o._container, return true);
			return _node == o._node;
		}
	};
	// INNER CLASS }
	// PROTECTED }
};
// CLASS slist }
// FUNCTION swap (for slist) {
template<typename Type, typename Allocate>
inline void swap(slist<Type, Allocate> &left, slist<Type, Allocate> &right)
{
	left.swap(right);
}
// FUNCTION swap (for slist) }
#endif // _KL_USE_FWD_LIST_

KL_END
#endif // __STD_FWD_LIST_H_VERSION_KL__
